package cc.willrock.algorithm.sort;

import java.util.Arrays;

public class Mediansort {
	public static int[] sort(int[] dest,int left,int right) {
		if(left< right){
			
			int mid =(right-left+1)/2; 
			int me = selectKth(dest, mid+1, left, right);
			sort(dest,  left, left+mid-1);
			sort(dest,  left+mid+1, right);
		}
		return dest;
	}

	/*
	 * 最好O(n) 平均O(n) 最坏O(n×n)
	 */
	public static int selectKth(int ar[], int k, int left, int right) {
		int pivotIndex = partition(ar, left, right);
		if (left + k - 1 == pivotIndex) {
			return pivotIndex;
		}
		if (left + k - 1 < pivotIndex) {
			return selectKth(ar, k, left, pivotIndex - 1);
		} else {
			return selectKth(ar, k - (pivotIndex - left + 1), pivotIndex + 1,
					right);
		}
	}

	//将left到right分成两个数组
	public static int partition(int[] pData, int left, int right) {
		// p = select pivot in A[left,right]
		int p = (left + right) / 2;
		// swap A[p] and A[right]
		int temp = pData[p];
		pData[p] = pData[right];
		pData[right] = temp;
		int store = left;

		for (int i = left; i < right; i++) {
			if (pData[i] <= pData[right]) {
				temp = pData[i];
				pData[i] = pData[store];
				pData[store] = temp;
				store++;
			}
		}
		temp = pData[right];
		pData[right] = pData[store];
		pData[store] = temp;

		return store;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int a[] = { 15, 9, 8, 1, 4, 11, 7, 12, 13, 6, 5, 3, 16, 2, 10, 14 };
		//int[] a = { 5, 1, 3, 2, 4 };
		System.out.println(a[selectKth(a,16,0,15)]);
		//System.out.println(Arrays.toString(sort(a,0,a.length-1)));
		//System.out.println(Arrays.toString(sort(a)));
		
		

	}

}
